#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
#http://www.careercup.com/question?id=14991189
#Google interview question
"""
Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time. (n >=0 ) You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo
"""
from collections import defaultdict
def find_elements(arr):
    counter = defaultdict(int)
    for i in arr:
        counter[i] += 1
        if len(counter) < 3: continue
        for k in counter.keys():
            if counter[k] == 1: del counter[k]
            else: counter[k] -= 1
    for k in counter.iterkeys(): counter[k] = 0
    for i in arr:
        if i in counter: counter[i] += 1
    result = []
    for k, count in counter.iteritems():
        if count > len(arr) / 3: result.append(k)
    return result

from utils import *
arr = random_arr(16, 0, 4)
print arr
print find_elements(arr)
